#!/usr/bin/env python
# -*- coding: utf-8 -*-

def merge(left, right):
    l_p, r_p = 0, 0;
    result = [];
    l_len, r_len = len(left), len(right);
    while l_p < l_len and r_p < r_len:
        if left[l_p] < right[r_p]:
            result.append(left[l_p]);
            l_p += 1;
        else:
            result.append(right[r_p]);
            r_p += 1;
    result += left[l_p:];
    result += right[r_p:];
    return result;

def sort(arr):
    length = len(arr);
    if length <= 1:
        return arr;
    mid = length / 2;
    left = sort(arr[:mid]);
    right = sort(arr[mid:]);
    return merge(left, right);

def main():
    arr = [9, 2, 1, 7, 6, 8, 5, 3, 4];
    print arr;
    result = sort(arr);
    print result;
    
if __name__ == '__main__':
    main();